package leetcode100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class lc049 {
    public static void main(String[] args) {
        Tree tree = new Tree();
        TreeNode root = tree.root;
        List<List<Integer>> lists = new lc049().levelOrder(root);
        System.out.println("lists = " + lists);
        ;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root==null)
            return res;

        List<Integer> level = new ArrayList<>();
//        List<Integer> lastLevel = new ArrayList<>();

        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<TreeNode> lastQueue = new LinkedList<>();


        lastQueue.add(root);

        while(!lastQueue.isEmpty()) {
            TreeNode cur = lastQueue.poll();
            level.add(cur.val);
            if (cur.left!=null) {
                queue.add(cur.left);
            } if(cur.right!=null) {
                queue.add(cur.right);
            }

//            System.out.println("cur = " + cur);
//            System.out.println("lastQueue = " + lastQueue);
//            System.out.println("queue = " + queue);
//            System.out.println("level = " + level);



            if (lastQueue.isEmpty()) {
                res.add(new ArrayList<>(level));
                level.clear();
                lastQueue = queue;
                queue=new LinkedList<>();
            }

        }




        return res;
    }
}
